/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/6/9.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 面试题46. 把数字翻译成字符串
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，
 * 1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
 * 一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有
 * 多少种不同的翻译方法。
 *
 * 示例 1:
 * 输入: 12258
 * 输出: 5
 * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 *
 * 提示：
 * 0 <= num < 2^31
 */
#include <iostream>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <cmath>

using namespace std;

class Solution {
public:
    static int translateNum(int num) {
        if(num == 0) return 1;
//        return rec_opt(num, 1 + (int) log10(num));
        return dp_opt(num);
    }

    /* 递归版本 */
    static int rec_opt(int num, int len) {
        /* 出口： 当长度不可再分时，说明可以成功翻译，返回一种新的翻译情况 */
        if(len == 0) {
//            cout << ">> " << num << endl;
            return 1;
        }

        /* 十位数的情况 */
        int a = rec_opt(num / 10, len - 1);
        /* 百位数的情况 */
        int b = 0;
        int m;
        if(len == 2 && num <= 25)                   /* 长度为 2，且百位数小于等于 25，肯定可分 */
            b = 1;
        else if(len > 2 && (m = num % 100) <= 25 && m >= 10) {   /* 只有在长度大于 2 时，且百位数在 0 ~ 25 范围内，才可再分  */
            b = rec_opt(num / 100, len - 2);
        }
        /* 返回当前数字下，十位数翻译情况个数 + 百位数翻译情况个数 */
        return a + b;
    }

    /* 动态规划版本 */
    static int dp_opt(int num) {
        string ns = to_string(num);
        int ns_size = ns.size();
        int dp[ns_size + 1];
        dp[0] = dp[1] = 1;
        for(int i = 2; i < ns_size + 1; ++i) {
            int tmp = (ns[i - 2] - '0') * 10 + (ns[i - 1] - '0');
//            cout << tmp << endl;
            if(tmp >= 10 && tmp <= 25) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[ns_size];
    }
};

int main() {
    cout << Solution::translateNum(12258) << endl;
    return 0;
}

